Transaction processing is a typical application for a data processing system. A transaction processing application may process and update information in a very large database and the performance of a transaction processing application may strongly depend on the latency for accesses to information in the database. A disk drive system may be required to provide sufficient storage to contain the entire database for a transaction processing application, but a disk drive system may adversely affect application performance because a disk drive system generally has a high access latency. In addition, performance of a data processing system may be affected by the latency of other accesses by the transaction processing application and other software on the data processing system, such as an operating system.
The performance of a data processing system may be improved by exploiting the temporal and spatial locality of the memory accesses by the data processing system. Memory access patterns often exhibit temporal locality because memory locations recently accessed are likely to soon be accessed again. Access patterns may also exhibit spatial locality because memory locations nearby memory locations already accessed are likely to also be accessed. For example, sequential accesses within a linear array have spatial locality.
Caches may be used to improve performance by exploiting the temporal and spatial locality of memory accesses to reduce the effective latency for memory accesses. Generally, the memory address space is broken into cache lines with each cache line larger than the largest possible access. A cache typically holds the cache lines containing the data that was most recently accessed. As the application on the data processing system accesses data, the data accessed that is not already in the cache is brought into the cache. Thus, after a cache line is brought into cache as a result of a data access, the data is available from the cache for subsequent accesses to the same data and subsequent accesses to nearby data on the cache line. When data for an access is available from a cache, the latency to access the data is reduced to the access latency for the cache. If the data is available from a cache for a significant portion of the accesses, the performance of a data processing system may be dramatically improved.
A trade-off made in designing a cache is that that a larger cache is likely to contain data for more of the accesses, but a larger cache is also likely to have a longer access latency. A hierarchy of caches may be used with the smaller and faster caches checked for the data before the larger and slower caches. The average effective latency for accesses may then be the sum of the products of the latency of each cache and memory times the respective fraction of the accesses fulfilled by the cache or memory.
Not all memory access patterns exhibit temporal and spatial locality. For example, the initialization of a large data structure, such as a database, may access more data than can be stored in all the caches in a data processing system. If the caches always store the most recently accessed information, the initialization of a large data structure may cause the caches to become filled with data for which locality of accesses is unlikely, and this data may displace data for which locality of accesses is likely, such that the initialization of a large data structure may reduce the effectiveness of the cache. An attribute may be associated with certain accesses that are expected to lack locality and the caches constructed to not store data for accesses having an attribute indicating lack of locality. However, the expected lack of locality may prove incorrect. For example, a large data structure may be copied and an attribute specifying a lack of locality for the large data structure may be incorrect when several copies are made in parallel.
A system that addresses these and other problems may therefore be desirable.